题解 CF292D 【Connected Components】

发表于 | 更新于

题意
一个无向图，给出$m$条边，有$k$次询问，每次询问将第$l_{i}$到$r_{i}$条边暂时删去，求这时候有多少个连通分量.$N\leqslant500,1\leqslant M,K\leqslant10000$

每次暴力建边(即建$1$ ~ $(l_{i}-1),(r_{i}+1)$ ~ $m$这些边)，用并查集维护的思路很好想，复杂度为$O(mk)$, 在卡常或是手动$O3$的情况下可以跑过，但并不是最优解。

我们发现很多边重复建了很多次，没有意义，于是我们只需要预处理出$1$ ~ $l_{i}$这些边连起来得到的并查集与$r_{i}$~$n$这些边连起来得到的并查集，将其合并，求出联通快即可。

难点：如何合并？

我们可以将左边i条边所得的并查集$l_{i}$直接复制到现在一个的并查集$f$中，然后，我们将现在正在处理的并查集中的每个元素和连右边$j$条边的并查集$r_{j}$的元素一一合并，得到一个新的并查集，这个新的并查集中集合的元素就是答案(统计有多少$f_{i}=i$即可)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define ll long long
#define sqr(x) ((x)*(x))
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int f[10005],l[10005][505],r[10005][505],x[10005],y[10005];
int find1(int i,int k){
    if (l[i][k]==k)return k;
    else return l[i][k]=find1(i,l[i][k]);
}
int find2(int i,int k){
    if (r[i][k]==k)return k;
    else return r[i][k]=find2(i,r[i][k]);
}
int find(int k){
    if (f[k]==k)return k;
    else return f[k]=find(f[k]);
}//三个数组的并查集操作
int main(){
    int n=read(),m=read();
    for (int j=1;j<=n;++j)
        l[0][j]=j,r[m+1][j]=j;//预处理
    for (int i=1;i<=m;++i){
        x[i]=read(),y[i]=read();
        for (int j=1;j<=n;++j)l[i][j]=l[i-1][j];
        int u=find1(i,x[i]),w=find1(i,y[i]);
        if (u!=w)l[i][u]=w;
    }
    for (int i=m;i;--i){
        for (int j=1;j<=n;++j)r[i][j]=r[i+1][j];
        int u=find2(i,x[i]),w=find2(i,y[i]);
        if (u!=w)r[i][u]=w;
    }
    int k=read();
    for (int i=1;i<=k;++i){
        int l1=read(),r1=read(),cnt=0;
        for (int i=1;i<=n;++i)f[i]=l[l1-1][i];//将l数组[l1-1]数组复制给f数组        
        for (int j=1;j<=n;++j)f[find(l[l1-1][j])]=find(r[r1+1][j]);//合并两个并查集
        for (int j=1;j<=n;++j)
            if (f[j]==j)
                ++cnt;//统计答案
        printf("%d\n",cnt);
    }
    return 0;
}